﻿//https://leetcode.cn/problems/russian-doll-envelopes/

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes)
    {
        //重新排序
        sort(envelopes.begin(), envelopes.end(), [&](const vector<int>& v1, const vector<int>& v2)
            {
                return v1[0] != v2[0] ? v1[0]<v2[0] : v1[1]>v2[1];
            });

        //贪心+二分
        vector<int> temp;
        temp.push_back(envelopes[0][1]);
        for (int i = 1; i < envelopes.size(); i++)
        {
            int b = envelopes[i][1];
            if (b > temp.back())
            {
                temp.push_back(b);
            }

            else
            {
                int left = 0, right = temp.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (temp[mid] >= b) right = mid;
                    else left = mid + 1;
                }
                temp[left] = b;
            }

        }

        return temp.size();

    }
};